<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Stack',
	'<{subtitle}>' => 'Written in <span title="Data Structures">CS 3303</span> by <a href="https://y.st./">Alexand(er|ra) Yst</a>, finalised on 2018-12-05',
	'<{copyright year}>' => '2018',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<p>
	Below is the code for my submission.
	The instructions were a bit unclear.
	The textual part says to push the value <code>0</code> three times.
	However, the included diagram shows that we need to push the values <code>2</code>, <code>1</code>, and <code>0</code>, in that order.
	I chose to use the three separate values, as this makes more sense.
	If we use the number <code>0</code> every time, there might as well not be a number at all.
</p>
<p>
	Three classes are defined; one to implement the stack, one to implement a link on the stack, and one to hold the main program code.
	List links do not need to be touched directly.
	Instead, the <code>Stack</code> class does all that for us.
	Pushing an item onto the stack in my algorithm simply saves the link to the old top item to a temporary variable, encapsulates the pushed number in a new link object, changes the link to the head of the stack to point to the new object, then saves a link to the old head of the stack in the new head of the stack.
	Regardless of the size of input, this takes a constant amount of time, or Θ(1).
	Pushing a number of items onto the stack would therefore take Θ(n), with n being the number of items pushed.
	Popping from the stack is similar.
	Again, that&apos;s Θ(1) for popping an item, making it Θ(n) for popping a number of items.
	The main difference between pushing and popping is that you can&apos;t pop an item off an empty stack.
	Trying to do that results in an error.
	In case you don&apos;t know if the stack is empty, I&apos;ve included an <code>IsEmpty()</code> method.
	It doesn&apos;t get called in the below program though, because we know how many items went onto the stack, so we know how many to pop back off.
</p>
<p>
	Without further ado, the code:
</p>
<blockquote>
<pre><code>/**
 * CS 3303 Unit 3 stack assignment submission
 * Copyright © 2018 Alex Yst &lt;mailto:copyright@y.st&gt;
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see &lt;https://www.gnu.org./licenses/&gt;.
**/

public class Node {
	Node pointer;
	int value;
	public Node(int value) {
		this.value = value;
	}
}

public class Stack {
	Node pointer;
	public void Push(int i) {
		if(this.pointer == null) {
			this.pointer = new Node(i);
		} else {
			Node old = this.pointer;
			this.pointer = new Node(i);
			this.pointer.pointer = old;
		}
	}
	public int Pop() {
		int value = this.pointer.value;
		this.pointer = this.pointer.pointer;
		return value;
	}
	
	public boolean IsEmpty() {
		return this.pointer == null;
	}
}

public class Unit3 {
	public static void main() {
// The program begins by pushing three items to the stack.
// The instructions say to push the number 0 three times.
// However, the diagram shows the numbers 2, 1, and 0 getting pushed, then popped in reverse order.
// It makes much more sense to push three numbers instead of the same number three times, so I&apos;m doing that.
		Stack stack = new Stack();
		stack.Push(2);
		stack.Push(1);
		stack.Push(0);

// Next, we pop the first item, and print it to the console.
// This is the first testing station.
		System.out.println(&quot;Testing station 0; item popped: &quot; + stack.Pop());

// Next, we pop the second item, and print it to the console.
// This is the second testing station.
		System.out.println(&quot;Testing station 1; item popped: &quot; + stack.Pop());

// Next, we pop the third item, and print it to the console.
// This is the third testing station.
		System.out.println(&quot;Testing station 2; item popped: &quot; + stack.Pop());
	}
}</code></pre>
</blockquote>
END
);
